package yyl.example.basic.algorithm.sort;

import java.util.Arrays;

/**
 * <h3>堆排序(Heap Sort)</h3><br>
 * 堆排序是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是一种改进选择排序的，改进的重点是减少关键码的比较次数。<br>
 * 堆排序是将数据看成是完全二叉树、根据完全二叉树的特性来进行排序的一种算法。<br>
 * 二叉堆有两种形式，大顶堆和小顶堆。<br>
 * 大顶堆是指：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列。<br>
 * 小顶堆是指：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列。<br>
 * 堆排序的实现过程分两步（以大顶堆为例）：<br>
 * 1.根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父节点都比它的子节点数值大）。<br>
 * 2.每次交换第一个和最后一个元素（将最大值放到末尾），然后把剩下元素重新调整为大顶堆。<br>
 * 堆排序的平均时间复杂度为 Ο(nlogn)。<br>
 * <br>
 * 堆的逻辑结构：<br>
 * ...................................<br>
 * ................{0}................<br>
 * .........┌───────┴───────┐.........<br>
 * ........{1}.............{2}........<br>
 * .....┌───┴───┐.......┌───┴───┐.....<br>
 * ....{3}.....{4}.....{5}.....{6}....<br>
 * ...┌─┴─┐...┌─┘.....................<br>
 * ..{7}.{8}.{9}......................<br>
 * ...................................<br>
 * 堆的物理结构：<br>
 * [{0},{1},{2},{3},{4},{5},{6},{7},{8},{9}]<br>
 * <br>
 * 从堆的结构可以看出，数组(二叉树)中的任意元素R[i]<br>
 * (1) 它的左子节点是：R[2*i+1];<br>
 * (2) 它的右子节点是：R[2*i+2];<br>
 * (3) 它的父节点是：R[(i-1)/2];<br>
 * (3) 如果是大顶堆： R[i] >= R[2*i+1] 且 R[i] >= R[2*i+2]。<br>
 * (4) 如果是小顶堆： R[i] <= R[2*i+1] 且 R[i] <= R[2*i+2]。<br>
 * (5) 二叉树节点总数为 n，则最后一个非叶子节点位置是 ((n-1)/2)-1 ;<br>
 * <br>
 * 最后一个非叶子节点位置推导过程<br>
 * 二叉树有两种情况<br>
 * ① 树的节点数为偶数时，堆的最后一个非叶子节点若只有左子节点；<br>
 * 设最后一个非叶子节点序号为i；<br>
 * 左子节点的序号为n-1，因为 n-1=(2*i)+1，推出i=(n/2)-1；<br>
 * ② 树的节点数为奇数时，堆的最后一个非叶子节点有左右两个子节点。<br>
 * 设最后一个非叶子节点序号为i；<br>
 * 左子节点的序号为n-2，根据 n-2=(2*i)+1，推出i=((n-1)/2)-1；<br>
 * 右子节点的序号为n-1，根据 n-1=(2*i)+2，推出i=((n-1)/2)-1；<br>
 * <br>
 * 因为JAVA语法的特征，整数除不尽时向下取整，则若n为奇数时(n-1)/2-1=n/2-1。<br>
 * 所以得到则最后一个非叶子节点位置是((n-1)/2)-1<br>
 */
public class HeapSort {

    public static void main(String[] args) {

        int[] array = Helper.generate(10);
        System.out.println(Arrays.toString(array));

        sort(array);
        System.out.println(Arrays.toString(array));
    }

    // 排序
    public static void sort(int[] array) {

        // 数组元素个数(二叉树节点个数)
        int length = array.length;

        // 建堆：从最后一个非叶子节点开始，向前进行调整，确保符合二叉树特性
        for (int i = (length / 2) - 1; i >= 0; i--) {
            heapify(array, i, length);
        }

        // 输出：从后向前进行 n-1 遍历
        for (int i = length - 1; i > 0; i--) {
            // 交换第一个元素和最后一个元素
            // 大顶堆，根节点(数组第一个元素)，一定是最大的数，将它放到数组最后
            int root = array[0];
            array[0] = array[i];
            array[i] = root;

            // 调整使剩余部分符合二叉树特性
            heapify(array, 0, i);
        }
    }

    // 节点调整，确保符合二叉树特性(升序，选择大顶堆)
    private static void heapify(int[] array, int parent, int length) {
        // 父节点数据
        int temp = array[parent];
        // 左侧子节点(因为如果数组长度是偶数，没有右子节点)
        int child = 2 * parent + 1;

        while (child < length) {
            // 如果有右子节点节点，并且右子节点节点的值大于左子节点，则选取右子节点
            if (child + 1 < length && array[child] < array[child + 1]) {
                child = child + 1;
            }
            // 父节点大于等于子节点(符合规则)
            if (temp >= array[child]) {
                break;
            }
            // 子节点数值赋给父节点数值
            array[parent] = array[child];

            // 从子节点开始，继续向下遍历
            parent = child;
            // 下一个左侧子节点
            child = 2 * parent + 1;
        }
        // 将最初保存的数插入最后这个节点的位置
        array[parent] = temp;
    }
}
